//////////////////////////////////////
// Fast Container Library           //
// MIT License - Copyright (c) 2012 //
//////////////////////////////////////

#pragma once

#include "common.h"
#include "iterator_traits.h"
#include "type_traits.h"
#include "utility.h"


FC_NAMESPACE_BEGIN


// binary_search.h (binary search operations on sorted ranges)
//
// lower_bound
// upper_bound
// equal_range
// binary_find
// binary_search


// lower_bound

template <class ForwardIterator, class T, class Compare> inline
	ForwardIterator lower_bound( ForwardIterator first, ForwardIterator last, const T& value, Compare compare )
	{
		typedef typename iterator_traits<ForwardIterator>::difference_type difference_type;
		difference_type dist = distance(first, last);

		while( dist > 0 )
		{
			const difference_type step = dist >> 1;
			ForwardIterator mid = first;
			fc::advance(mid, step);

			if( compare(*mid, value) )
				first = ++mid, dist -= step + 1;
			else
				dist = step;
		}

		return first;
	}

template <class ForwardIterator, class T> inline
	ForwardIterator lower_bound( ForwardIterator first, ForwardIterator last, const T& value )
	{
		typedef typename iterator_traits<ForwardIterator>::difference_type difference_type;
		difference_type dist = distance(first, last);

		while( dist > 0 )
		{
			const difference_type step = dist >> 1;
			ForwardIterator mid = first;
			fc::advance(mid, step);

			if( *mid < value )
				first = ++mid, dist -= step + 1;
			else
				dist = step;
		}

		return first;
	}


// upper_bound

template <class ForwardIterator, class T, class Compare> inline
	ForwardIterator upper_bound( ForwardIterator first, ForwardIterator last, const T& value, Compare compare )
	{
		typedef typename iterator_traits<ForwardIterator>::difference_type difference_type;
		difference_type dist = distance(first, last);

		while( dist > 0 )
		{
			const difference_type step = dist >> 1;
			ForwardIterator mid = first;
			fc::advance(mid, step);

			if( !compare(value, *mid) )
				first = ++mid, dist -= step + 1;
			else
				dist = step;
		}

		return first;
	}

template <class ForwardIterator, class T> inline
	ForwardIterator upper_bound( ForwardIterator first, ForwardIterator last, const T& value )
	{
		typedef typename iterator_traits<ForwardIterator>::difference_type difference_type;
		difference_type dist = distance(first, last);

		while( dist > 0 )
		{
			const difference_type step = dist >> 1;
			ForwardIterator mid = first;
			fc::advance(mid, step);

			if( !(value < *mid) )
				first = ++mid, dist -= step + 1;
			else
				dist = step;
		}

		return first;
	}


// equal_range

template <class ForwardIterator, class T, class Compare> inline
	pair<ForwardIterator, ForwardIterator>
	equal_range( ForwardIterator first, ForwardIterator last, const T& value, Compare compare )
	{
		ForwardIterator it1 = lower_bound( first, last, value, compare );
		ForwardIterator it2 = upper_bound( it1, last, value, compare );
		return pair<ForwardIterator, ForwardIterator>(it1, it2);
	}

template <class ForwardIterator, class T> inline
	pair<ForwardIterator, ForwardIterator>
	equal_range( ForwardIterator first, ForwardIterator last, const T& value )
	{
		ForwardIterator it1 = lower_bound( first, last, value );
		ForwardIterator it2 = upper_bound( it1, last, value );
		return pair<ForwardIterator, ForwardIterator>(it1, it2);
	}


// binary_find

template <class InputIterator, class T> inline
	InputIterator binary_find( InputIterator first, InputIterator last, const T& value )
	{
		first = lower_bound(first, last, value);
		return (first != last && !(value < *first)) ? first : last;
	}

template <class InputIterator, class T, class Compare> inline
	InputIterator binary_find( InputIterator first, InputIterator last, const T& value, Compare compare )
	{
		first = lower_bound(first, last, value, compare);
		return (first != last && !(value < *first)) ? first : last;
	}


// binary_search

template <class InputIterator, class T> inline
	bool binary_search( InputIterator first, InputIterator last, const T& value )
	{
		return binary_find(first, last, value) == last ? false : true;
	}

template <class InputIterator, class T, class Compare> inline
	bool binary_search( InputIterator first, InputIterator last, const T& value, Compare compare )
	{
		return binary_find(first, last, value, compare) == last ? false : true;
	}


FC_NAMESPACE_END